from typing import List

class Solution: 
    def squareRoot11(self, n):
        num = []        
        den = []
        num.append(3)
        den.append(1)
        if n == 0: 
            return num[0], den[0] 
        num.append(10)
        den.append(3)
        if n == 1: 
           return num[1], den[1] 

        count = 2 
        while count <= n: 
            # print(f"count is {count}")
            # print(f"num is {num}")
            # print(f"den is {den}")

            if count % 2 == 0: 
                mul = 6 
            else: 
                mul = 3 
            temp = num[1]
            num[1] = mul * num[1] + num[0]
            num[0] = temp 
            
            temp = den[1]
            den[1] = mul * den[1] + den[0]
            den[0] = temp 

            count += 1  

        return num[-1], den[-1]

if __name__ == "__main__": 
    s = Solution()
    n = 2 
    x, y = s.squareRoot11(n)
    assert x == 63 
    assert y == 19

    n = 3
    x, y = s.squareRoot11(n)
    assert x == 199
    assert y == 60
